/* 
文件 shdl.c
作者 lee8871@126.com
shdl 实现了单向(single way) 头指针控制(head pointer) 偏移量引导(diff) 链表(linked list) 的基本操作。
*/



#include "shdl.h"
#define nullptr 0





#define NEXT(NODE) *((tPtr*)(next_diff + (char*)NODE))
void Linklist_append(tPtr* head, char next_diff, tPtr new_node) {
    if(*head == nullptr) {// 如果头节点为空，直接添加
        *head = new_node;
        NEXT(new_node) = nullptr; // 确保新节点的下一个指针为 nullptr        
    } else {
        tPtr current = *head ; // 从头节点开始
        while (NEXT(current) != nullptr) {
            current = NEXT(current);
        }
        NEXT(current) = new_node; // 将新节点添加到链表末尾
        NEXT(new_node) = nullptr; // 确保新节点的下一个指针为 nullptr     
    }
}      
// 在链表头部插入节点
void Linklist_prepend(tPtr* head, char next_diff, tPtr new_node) {
    NEXT(new_node) = *head;
    *head = new_node;
}

tPtr Linklist_removeFirst(tPtr* head, char next_diff){
    tPtr removed_node = *head; // 保存要删除的节点
    if (removed_node == nullptr) {
        return nullptr; // 如果链表为空，返回 nullptr
    }
    *head = NEXT(removed_node); // 更新头节点为下一个节点
    NEXT(removed_node) = nullptr; // 清除被删除节点的下一个指针
    return removed_node; // 返回被删除的节点
}


tPtr Linklist_removeLast(tPtr* head, char next_diff){
    if (*head == nullptr) {
        return nullptr; // 如果链表为空，返回 nullptr
    }    
    tPtr current = *head;
    if (NEXT(current) == nullptr) {
        *head = nullptr; // 如果只有一个节点，清空链表
        return current; // 返回被删除的节点
    }
    while (NEXT(NEXT(current)) != nullptr) {
        current = NEXT(current); // 找到倒数第二个节点
    }
    tPtr removed_node = NEXT(current); // 保存要删除的节点
    NEXT(current) = nullptr; // 将倒数第二个节点的下一个指针    
    return removed_node; // 返回被删除的节点
}
enum sIterateCtrl {
    eIterateCtrl_Continue = 0, // 继续遍历
    eIterateCtrl_Stop = 1,     // 停止遍历
    eIterateCtrl_Remove = 2,   // 删除当前节点并继续遍历
    eIterateCtrl_RemoveStop = 3 // 删除当前节点并停止遍历
};
/**
 * 遍历链表并对每个节点执行回调函数
 * @param head 链表头指针
 * @param callback 对每个节点执行的回调函数，参数为节点指针和用户提供的数据
 * @param next_diff next指针在节点结构中的偏移量
 * @param tag 传递给回调函数的用户自定义数据
 * @return 被回调函数终止遍历的节点序号（从0开始），或链表长度（如果遍历完成）
 */
int Linklist_foreach(tPtr* head, char next_diff, int (*callback)(tPtr node, void* tag), void* tag) {
    tPtr current = *head;
    int count = 0;
    while (current != nullptr) {
        if (callback(current, tag) != eIterateCtrl_Continue) {
            return count;
        }        
        current = NEXT(current);
        count++;
    }
    
    return count;  // 返回链表长度
}
/**
 * 遍历链表并删除所有符合条件的节点
 * @param head 链表头指针的指针
 * @param next_diff next指针在节点结构中的偏移量
 * @param predicate 判断函数，对每个节点进行检查，如果返回非零值则删除该节点
 * @param tag 传递给判断函数的用户自定义数据
 * @return 删除的节点数量
 */
int Linklist_removeIf(tPtr* head, char next_diff, int (*predicate)(tPtr node, void* tag), void* tag) {
    if (head == nullptr) {
        return 0; 
    }
    tPtr virtual_first_node;//创建一个虚拟的头节点，地址是head的地址向前next_diff
    virtual_first_node = (tPtr)((char*)head - next_diff);

    int removed_count = 0;
    tPtr current = virtual_first_node;
    
    while (NEXT(current) != nullptr) {
        tPtr target = NEXT(current);
        tPtr target_next = NEXT(target);
        NEXT(target) = nullptr; //暂时清除被删除节点的next指针
        int ctrl = predicate(target, tag);// 调用判断函数，如果判断函数要求删除，则本程序后面不能再操作tartget。
        if(ctrl == eIterateCtrl_RemoveStop || ctrl == eIterateCtrl_Remove) {
            NEXT(current) = target_next; //连接链表，确实删除元素
            removed_count++;
            //由于删除了元素，下一个和需要处理的仍然是NEXT(current) 
        }else{
            NEXT(target) = target_next; //恢复链表
            current = target; //由于没有删除元素，下一个要处理的将是NEXT(target)，因此链表向前移动
        }
        if(ctrl == eIterateCtrl_RemoveStop|| ctrl == eIterateCtrl_Stop) {//如果要求结束搜索
            return removed_count;
        }
    }
    return removed_count;
}
